package leetcode.D1000.T990;

import java.util.HashMap;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-18 23:21:56 星期五
 */

class Solution {
    public boolean equationsPossible(String[] equations) {
        int count = 0;
        Map<Character, Integer> charToInt = new HashMap<>();
        for(String equation : equations) {
            char a = equation.charAt(0);
            char b = equation.charAt(3);
            if(!charToInt.containsKey(a)) {
                charToInt.put(a, count++);
            }
            if(!charToInt.containsKey(b)) {
                charToInt.put(b, count++);
            }
        }
        UnionFindSet unionFindSet = new UnionFindSet(count);
        for(String equation : equations) {
            int ia = charToInt.get(equation.charAt(0));
            int ib = charToInt.get(equation.charAt(3));
            if(equation.charAt(1) == '=') {
                unionFindSet.union(ia, ib);
            }
        }
        for(String equation : equations) {
            int ia = charToInt.get(equation.charAt(0));
            int ib = charToInt.get(equation.charAt(3));
            if(equation.charAt(1) == '!' && unionFindSet.isConnected(ia, ib)) {
                return false;
            }
        }
        return true;
    }
}

class UnionFindSet {
    private int[] father;
    public UnionFindSet(int n) {
        father = new int[n];
        for(int i=0; i<n; ++i) {
            father[i] = i;
        }
    }
    private int find(int i) {
        if(i == father[i]) return i;
        int fa = find(father[i]);
        father[i] = fa;
        return fa;
    }
    public boolean isConnected(int a, int b) {
        return find(a) == find(b);
    }
    public void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        father[fa] = fb;
    }
}
